package arithmetic.demo26;

/**
 * 动态规划：位置dp + 似包非包： 组合总和（IV）
 */

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 动态规划 + 01背包
        int len = nums.length;

        // 创建 dp
        int[] dp = new int[target + 1];
        // 如果 i = 0 或者 j = 0 可以为 1 种情况
        dp[0] = 1;

        // 遍历每一个位置
        for(int j = 0; j <= target ; j++) {
            // 每一个位置可以挑选的种类
            for(int i = 1; i <= len; i++) {

                if(j >= nums[i-1]) {
                // 累加上前面的个数
                dp[j] += dp[j - nums[i - 1]];
            
                }
                
            }
        }

        return dp[target];
    }
}


/**
 * 动态规划： 抽象状态表示 + 含义dp ：不同的二次搜索树
 */
class Solution1 {
    public int numTrees(int n) {
        // 动态规划 + 抽象状态表示
        // 创建 dp
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 1;
        // 填表
        for(int i  = 2; i <= n; i++) {
            for(int j = 1; j <= i ; j++) {
                // 先确定以 i 位置为根结点的个数
                // 最终加上每个以 i 位置为根节点的情况个数
                dp[i] += dp[j-1] * dp[i-j];

            }

        }

        return dp[n];
    }
}